package L617;

import util.TreeNode;

import java.util.ArrayList;
import java.util.List;

/**
 * @program: javase
 * @description: 给你二叉树的根节点 root 和一个整数目标和 targetSum ，
 * 找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。
 * @author: luolidong
 * @create: 2021-06-17 09:42
 * @version: 1.0
 */
public class Demo {
    List<List<Integer>> list = new ArrayList<>();

    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        dfs(root, targetSum, new ArrayList<>());
        return list;
    }
    public void dfs(TreeNode root, int targetSum,List<Integer> clist){
        if(root==null) return;
        targetSum-=root.val;
        clist.add(root.val);
        if(root.left==null&&root.right==null&&targetSum==0){
            list.add(new ArrayList<>(clist));
        }
        dfs(root.left, targetSum, clist);
        dfs(root.right, targetSum, clist);
        clist.remove(clist.size()-1);
        targetSum+=root.val;
    }

    public static void main(String[] args) {
        List<List<Integer>> list = new Demo().pathSum(TreeNode.build(), 8);
        for(List<Integer> l:list){
            System.out.println(l);
        }
    }
}
